package main

import (
	"fmt"
	"sort"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

var (
	intersectNum1   = []int{4, 9, 5}
	intersectNum2   = []int{9, 4, 9, 8, 4}
	checkDuplicated = []int{1, 2, 3, 4}

	uniqCharInStr = "ddaaaaad"

	// construct nodeList
	nodeTail = &ListNode{
		9,
		nil,
	}
	nodeTail1 = &ListNode{
		1,
		nodeTail,
	}
	nodeTail2 = &ListNode{
		5,
		nodeTail1,
	}
	nodeHead = &ListNode{
		4,
		nodeTail2,
	}
)

func backTrain() {
	fmt.Println("Welcome back!")

	// delete node from nodeList
	deleteNode(nodeTail1)
	fmt.Println(nodeTail2.Next)
	return

	// uniq char in str
	fmt.Println(firstUniqChar(uniqCharInStr))

	// check duplicated
	fmt.Println(containsDuplicate(checkDuplicated))

	// intersect
	fmt.Println(intersect(intersectNum1, intersectNum2))
	fmt.Println(intersectMap(intersectNum1, intersectNum2))
}

func intersect(nums1 []int, nums2 []int) []int {
	ret := []int{}

	l1 := len(nums1)
	l2 := len(nums2)

	offset1 := 0
	offset2 := 0

	for offset1 < l1 && offset2 < l2 {
		for i := offset2; i < l2; i++ {
			// fmt.Printf("--: %v | %v \n", nums1[offset1], nums2[offset2])
			if nums1[offset1] == nums2[i] {
				ret = append(ret, nums1[offset1])
				nums2[i] = nums2[offset2]
				offset2++
				break
			}
		}

		offset1++
	}

	return ret
}

func intersectMap(nums1 []int, nums2 []int) []int {
	ret := []int{}
	map1 := make(map[int]int)
	map2 := make(map[int]int)

	for _, v := range nums1 {
		map1[v]++
	}

	for _, v := range nums2 {
		map2[v]++
	}

	for k, v := range map1 {
		if value, ok := map2[k]; ok {
			size := v
			if value < size {
				size = value
			}

			for i := 0; i < size; i++ {
				ret = append(ret, k)
			}
		}
	}

	return ret
}

func containsDuplicate(nums []int) bool {
	sort.Ints(nums)
	l := len(nums)

	for i := 0; i < (l - 1); i++ {
		if nums[i] == nums[i+1] {
			return true
		}
	}

	return false
}

func firstUniqChar(s string) int {
	m1 := make(map[byte]int)
	for k, _ := range s {
		m1[s[k]]++
	}

	l := len(s)
	for i := 0; i < l; i++ {
		if m1[s[i]] == 1 {
			return i
		}
	}

	return -1
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteNode(node *ListNode) {
	node.Val = node.Next.Val
	node.Next = node.Next.Next
}
